{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #List of Depth LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #linked-list #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #链表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: listOfDepth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特定深度节点链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 <code>D</code>，则会创建出 <code>D</code> 个链表）。返回一个包含所有深度的链表的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[1,2,3,4,5,null,7,8]\n",
    "\n",
    "        1\n",
    "       /  \\ \n",
    "      2    3\n",
    "     / \\    \\ \n",
    "    4   5    7\n",
    "   /\n",
    "  8\n",
    "\n",
    "<strong>输出：</strong>[[1],[2,3],[4,5,7],[8]]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [list-of-depth-lcci](https://leetcode.cn/problems/list-of-depth-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [list-of-depth-lcci](https://leetcode.cn/problems/list-of-depth-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,null,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        q = deque()\n",
    "        res = []\n",
    "        q.append(tree)\n",
    "        while q:\n",
    "            dummy = ListNode(None)\n",
    "            p = dummy\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                listnode = ListNode(node.val)\n",
    "                p.next = listnode\n",
    "                p = p.next\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(dummy.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        def dfs(node, level):\n",
    "            if not node: return None\n",
    "            if len(ans) == level:\n",
    "                ans.append(ListNode(node.val))\n",
    "            else:\n",
    "                head = ListNode(node.val)\n",
    "                head.next = ans[level]\n",
    "                ans[level] = head\n",
    "            dfs(node.right, level + 1)\n",
    "            dfs(node.left, level + 1)\n",
    "        dfs(tree, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        d = deque()\n",
    "        d.append(tree)\n",
    "        ans = []\n",
    "        while d:\n",
    "            end = head = ListNode()\n",
    "            for i in range(len(d)):\n",
    "                cur = d.pop()\n",
    "                end.next = ListNode(cur.val)\n",
    "                end = end.next\n",
    "                if cur.left:d.appendleft(cur.left)\n",
    "                if cur.right:d.appendleft(cur.right)\n",
    "            ans.append(head.next)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "  def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "    res = []\n",
    "    now = []\n",
    "    def dfs(tree,d):\n",
    "      if not tree: return\n",
    "      if d==len(now):\n",
    "        now.append(ListNode(tree.val))\n",
    "        res.append(now[d])\n",
    "      else:\n",
    "        now[d].next=ListNode(tree.val)\n",
    "        now[d] = now[d].next\n",
    "      dfs(tree.left,d+1)\n",
    "      dfs(tree.right,d+1)\n",
    "    dfs(tree,0)\n",
    "    return res\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        queue = []\n",
    "        queue.append(tree)\n",
    "        while queue:\n",
    "            temp = ListNode()\n",
    "            r = temp\n",
    "            for i in range(len(queue)):\n",
    "                q = queue.pop(0)\n",
    "                ne = ListNode(q.val)\n",
    "                if q.left:\n",
    "                    queue.append(q.left)\n",
    "                if q.right:\n",
    "                    queue.append(q.right)\n",
    "                temp.next = ne\n",
    "                temp = temp.next\n",
    "            res.append(r.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        if not tree:\n",
    "            return ans\n",
    "        q = deque([tree])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            dummyhead = ListNode(-1)\n",
    "            listnode = dummyhead\n",
    "            for _ in range(n):\n",
    "                node = q.popleft()\n",
    "                listnode.next = ListNode(node.val)\n",
    "                listnode = listnode.next\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(dummyhead.next)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "\n",
    "        queen = []\n",
    "        res = []\n",
    "        queen.append(tree)\n",
    "        while queen:\n",
    "            tmp_dump = ListNode(0) \n",
    "            tmp_node =  tmp_dump\n",
    "            for _ in range(len(queen)):\n",
    "                node = queen.pop(0)\n",
    "                tmp_node.next = ListNode(node.val)\n",
    "                tmp_node = tmp_node.next\n",
    "                if node.left: queen.append(node.left)\n",
    "                if node.right: queen.append(node.right)\n",
    "            res.append(tmp_dump.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue = []\n",
    "        results = []\n",
    "\n",
    "        queue.append(tree)\n",
    "\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            head = ListNode()\n",
    "            pre = None\n",
    "            for i in range(length):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                nod = ListNode(node.val)\n",
    "                if i == 0:\n",
    "                    head = nod\n",
    "                if pre:\n",
    "                    pre.next = nod\n",
    "                pre = nod\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            results.append(head)\n",
    "\n",
    "        return results\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        que=deque([tree])\n",
    "        ans=[]\n",
    "        while len(que)>0:\n",
    "            cur=dummy=ListNode()\n",
    "            for _ in range(len(que)):\n",
    "                node=que.popleft()\n",
    "                cur.next=ListNode(node.val)\n",
    "                cur=cur.next\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            ans.append(dummy.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        q = deque()\n",
    "        q.append(tree)\n",
    "        ans = []\n",
    "        while q:\n",
    "            length = len(q)\n",
    "            cur = ListNode(-1)\n",
    "            head = cur\n",
    "            for i in range(length):\n",
    "                x = q.popleft()\n",
    "                if x.left:\n",
    "                    q.append(x.left)\n",
    "                if x.right:\n",
    "                    q.append(x.right)\n",
    "                cur.next = ListNode(x.val)\n",
    "                cur = cur.next\n",
    "            ans.append(head.next)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if tree is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = [tree]\n",
    "        while len(q) > 0:\n",
    "            d = ListNode()\n",
    "            r = d\n",
    "            t = []\n",
    "            for node in q:\n",
    "                r.next = ListNode(node.val)\n",
    "                if node.left:\n",
    "                    t.append(node.left)\n",
    "                if node.right:\n",
    "                    t.append(node.right)\n",
    "                r = r.next\n",
    "            q = t\n",
    "            ans.append(d.next)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        if tree is None: return res\n",
    "        que = deque([tree])\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            pre = ListNode(-1)\n",
    "            res.append(pre)\n",
    "            while size:\n",
    "                node = que.popleft()\n",
    "                res[-1].next = ListNode(node.val)\n",
    "                res[-1] = res[-1].next\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "                size -= 1\n",
    "            res[-1] = pre.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        # 层次遍历\n",
    "\n",
    "        res = []\n",
    "        queue = []\n",
    "        queue.append(tree)\n",
    "        \n",
    "        while queue:\n",
    "            \n",
    "            size = len(queue)\n",
    "            head = ListNode(0)\n",
    "            cur = head\n",
    "            while size:\n",
    "                node = queue.pop()\n",
    "\n",
    "                size -=1\n",
    "                \n",
    "                cur.next  = ListNode(node.val)\n",
    "\n",
    "                cur = cur.next\n",
    "\n",
    "                if node.left:\n",
    "                    queue.insert(0,node.left)\n",
    "                if node.right:\n",
    "                    queue.insert(0,node.right)\n",
    "            res.append(head.next)\n",
    "        return res\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        '''\n",
    "        广度优先搜索\n",
    "        '''\n",
    "        res = []\n",
    "        q = collections.deque()\n",
    "\n",
    "        q.append(tree)\n",
    "\n",
    "        while q:\n",
    "            head = ListNode(-1)\n",
    "            cur = head \n",
    "\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                cur.next = ListNode(node.val)\n",
    "                cur = cur.next \n",
    "\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "\n",
    "                \n",
    "            res.append(head.next)\n",
    "\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]: # 用队列实现广度优先算法\n",
    "\n",
    "        que = collections.deque()\n",
    "        que.append(tree)\n",
    "        res = []\n",
    "        while que:\n",
    "            temp = ListNode(0)\n",
    "            dummy = temp\n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                temp.next = ListNode(node.val) # 当前层节点的val，记录在temp\n",
    "                temp = temp.next\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "            # 结束这一层，就记录这一层的结果\n",
    "            res.append(dummy.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        q = deque()\n",
    "        q.append(tree)\n",
    "        while q:\n",
    "            dummy = ListNode(None)\n",
    "            p = dummy\n",
    "            for _ in range(len(q)):\n",
    "                treenode = q.popleft()\n",
    "                listNode = ListNode(treenode.val)\n",
    "                p.next = listNode\n",
    "                p = p.next\n",
    "                if treenode.left:q.append(treenode.left)\n",
    "                if treenode.right:q.append(treenode.right)\n",
    "            res.append(dummy.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue=[tree]\n",
    "        res=[]\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                node=queue.pop(0)\n",
    "                if i==0:\n",
    "                    mynode=ListNode(node.val)\n",
    "                    res.append(mynode)\n",
    "                if i<size-1:\n",
    "                    next_node=ListNode(queue[0].val)\n",
    "                    mynode.next=next_node\n",
    "                    mynode=next_node\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:return\n",
    "        ans = []\n",
    "        q = [tree]\n",
    "        while q:\n",
    "            cur = head = ListNode()\n",
    "            for i in range(len(q)):\n",
    "                if q[i].left:q.append(q[i].left)\n",
    "                if q[i].right:q.append(q[i].right)\n",
    "                cur.next = ListNode(q[i].val)\n",
    "                cur = cur.next\n",
    "            ans.append(head.next)\n",
    "            q = q[i+1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "\n",
    "        def listToListNode(lst):\n",
    "            if not lst:\n",
    "                return None\n",
    "            pre = ListNode(-1)\n",
    "            new = pre\n",
    "            cur  = None\n",
    "            while lst:\n",
    "                cur = ListNode(lst.pop(0))\n",
    "                pre.next = cur\n",
    "                pre = cur\n",
    "            return new.next\n",
    "\n",
    "        queue = [tree]\n",
    "        res = []\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            node = None\n",
    "            ans = []\n",
    "            for i in range(l):\n",
    "                node = queue.pop(0)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            res.append(listToListNode(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        que = deque([tree])\n",
    "        ans = []\n",
    "        while que:\n",
    "            dummy = ListNode(-1)\n",
    "            node = dummy\n",
    "            L = len(que)\n",
    "            for i in range(L):\n",
    "                treenode = que.popleft()\n",
    "                node.next = ListNode(treenode.val)\n",
    "                node = node.next\n",
    "                if treenode.left:\n",
    "                    que.append(treenode.left)\n",
    "                if treenode.right:\n",
    "                    que.append(treenode.right)\n",
    "            ans.append(dummy.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode):\n",
    "        import queue\n",
    "        result = list()\n",
    "        que = queue.Queue()\n",
    "        que.put(tree)\n",
    "        while not que.empty():\n",
    "            size = que.qsize()\n",
    "            # 记录当前行\n",
    "            curr = ListNode(-1)\n",
    "            mark = curr\n",
    "            while size > 0:\n",
    "                # 取出一个添加到链表中\n",
    "                item = que.get()\n",
    "                curr.next = ListNode(item.val)\n",
    "                curr = curr.next\n",
    "                # 将子节点加入队列\n",
    "                if item.left:\n",
    "                    que.put(item.left)\n",
    "                if item.right:\n",
    "                    que.put(item.right)\n",
    "                \n",
    "                size -= 1\n",
    "            result.append(mark.next)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        q=deque()\n",
    "        q.append(tree)\n",
    "        ans=[]\n",
    "        while(q):\n",
    "            pre=ListNode()\n",
    "            t=pre\n",
    "            for _ in range(len(q)):\n",
    "                m=q.popleft()\n",
    "                temp=ListNode(m.val)\n",
    "                t.next=temp\n",
    "                t=t.next\n",
    "                if m.left:\n",
    "                    q.append(m.left)\n",
    "                if m.right:\n",
    "                    q.append(m.right)\n",
    "            ans.append(pre.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "\n",
    "        queue = deque([tree])\n",
    "        while queue:\n",
    "            cur = dummy = ListNode(-1)\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                cur.next = ListNode(val=node.val)\n",
    "                cur = cur.next\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            ans.append(dummy.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        answer = []\n",
    "\n",
    "        if tree != None:\n",
    "            stack = [tree]\n",
    "            while stack:\n",
    "                tmp = []\n",
    "                for x in stack:\n",
    "                    node = ListNode(val=x.val)\n",
    "                    tmp.append(node)\n",
    "                last = None\n",
    "                while tmp:\n",
    "                    node = tmp.pop(-1)\n",
    "                    node.next = last\n",
    "                    last = node\n",
    "                answer.append(last)\n",
    "                \n",
    "                _list = []\n",
    "                for x in stack:\n",
    "                    if x.left != None:\n",
    "                        _list.append(x.left)\n",
    "                    if x.right != None:\n",
    "                        _list.append(x.right)\n",
    "                stack[:] = _list[:]\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if tree is None:\n",
    "            return []\n",
    "        q = deque([tree])\n",
    "        res = []\n",
    "        head = ListNode()\n",
    "        while q:\n",
    "            pointer = head\n",
    "            for i in range(len(q)):\n",
    "                front = q.popleft()\n",
    "                pointer.next = ListNode(front.val)\n",
    "                pointer = pointer.next\n",
    "                if front.left:\n",
    "                    q.append(front.left)\n",
    "                if front.right:\n",
    "                    q.append(front.right)\n",
    "            res.append(head.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        q = [tree]\n",
    "        if not tree:return ans\n",
    "        while q:\n",
    "            end = head = ListNode(0)\n",
    "            for i in range(len(q)):\n",
    "                if q[i].left:q.append(q[i].left)\n",
    "                if q[i].right:q.append(q[i].right)\n",
    "                cur = ListNode(q[i].val)\n",
    "                end.next = cur\n",
    "                end = cur\n",
    "            ans.append(head.next)\n",
    "            q = q[i+1:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "  def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "    res = []\n",
    "    now = []\n",
    "    def dfs(tree,d):\n",
    "      if not tree: return\n",
    "      if d==len(now):\n",
    "        now.append(ListNode(tree.val))\n",
    "        res.append(now[d])\n",
    "      else:\n",
    "        now[d].next=ListNode(tree.val)\n",
    "        now[d] = now[d].next\n",
    "      dfs(tree.left,d+1)\n",
    "      dfs(tree.right,d+1)\n",
    "    dfs(tree,0)\n",
    "    return res\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "\n",
    "        my_queue = [(tree, 0)]\n",
    "        last_level = -1\n",
    "        ans = []\n",
    "        link_root = None\n",
    "        link_node = link_root\n",
    "        while len(my_queue) != 0:\n",
    "            node, level = my_queue.pop(0)\n",
    "            if level != last_level:\n",
    "                if link_root is not None:\n",
    "                    ans.append(link_root)\n",
    "                # 新建link\n",
    "                link_root = ListNode(node.val)\n",
    "                link_node = link_root\n",
    "            else:\n",
    "                link_node.next = ListNode(node.val)\n",
    "                link_node = link_node.next\n",
    "            # ----\n",
    "            last_level = level\n",
    "            if node.left is not None:\n",
    "                my_queue.append((node.left, level + 1))\n",
    "            if node.right is not None:\n",
    "                my_queue.append((node.right, level + 1))\n",
    "        if link_root is not None:\n",
    "            ans.append(link_root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue = []\n",
    "        results = []\n",
    "\n",
    "        queue.append(tree)\n",
    "\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            head = ListNode()\n",
    "            pre = None\n",
    "            for i in range(length):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                nod = ListNode(node.val)\n",
    "                if i == 0:\n",
    "                    head = nod\n",
    "                if pre:\n",
    "                    pre.next = nod\n",
    "                pre = nod\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            results.append(head)\n",
    "\n",
    "        return results\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        cur = tree\n",
    "        res = []\n",
    "        q = []\n",
    "        q.append(cur)\n",
    "        while q:\n",
    "            dumpnode = ListNode(0)\n",
    "            curnode = dumpnode\n",
    "            for i in range(len(q)):\n",
    "                curnode.next = ListNode(q[0].val)\n",
    "                cur = q.pop(0)\n",
    "                if cur.left: q.append(cur.left)\n",
    "                if cur.right: q.append(cur.right)\n",
    "                curnode = curnode.next\n",
    "            res.append(dumpnode.next)\n",
    "        return res\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        ans = []\n",
    "        queue = collections.deque([tree])\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(ListNode(node.val))\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            # link\n",
    "            cur = 0\n",
    "            while cur + 1 < len(tmp):\n",
    "                tmp[cur].next = tmp[cur + 1]\n",
    "                cur += 1\n",
    "\n",
    "            if len(tmp) > 0:\n",
    "                ans.append(tmp[0])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:return\n",
    "\n",
    "        ans = []\n",
    "        q = [tree]\n",
    "        while q:\n",
    "            end = head = ListNode(0)\n",
    "            for i in range(len(q)):\n",
    "                if q[i].left:q.append(q[i].left)\n",
    "                if q[i].right:q.append(q[i].right)\n",
    "                end.next = ListNode(q[i].val)\n",
    "                end = end.next\n",
    "            ans.append(head.next)\n",
    "            q = q[i+1:]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        que = [tree]\n",
    "        ans = []\n",
    "        while(que):\n",
    "            n = len(que)\n",
    "            ans_this = ListNode(-1)\n",
    "            T = ans_this\n",
    "\n",
    "            for i in range(n):\n",
    "                k = que.pop(0)\n",
    "                tr = ListNode(k.val)\n",
    "                T.next = tr\n",
    "                T = T.next\n",
    "                if k.left:\n",
    "                    que.append(k.left)\n",
    "                if k.right:\n",
    "                    que.append(k.right)\n",
    "            \n",
    "            ans.append(ans_this.next)\n",
    "        \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        q = deque()\n",
    "        q.append(tree)\n",
    "        while q:\n",
    "            head = ListNode(None)\n",
    "            p = head\n",
    "            for _ in range(len(q)):\n",
    "                tmp = q.popleft()\n",
    "                node = ListNode(tmp.val)\n",
    "                p.next = node\n",
    "                p = p.next\n",
    "                if tmp.left:\n",
    "                    q.append(tmp.left)\n",
    "                if tmp.right:\n",
    "                    q.append(tmp.right)\n",
    "            res.append(head.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = deque([root])\n",
    "        result = []\n",
    "        current_level_head = ListNode(-1)\n",
    "        current_level_tail = current_level_head\n",
    "        \n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                new_node = ListNode(node.val)\n",
    "                current_level_tail.next = new_node\n",
    "                current_level_tail = new_node\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            result.append(current_level_head.next)\n",
    "            current_level_head.next = None\n",
    "            current_level_tail = current_level_head\n",
    "            \n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        if not tree:\n",
    "            return []\n",
    "        \n",
    "        stack = [tree]\n",
    "        count = 1\n",
    "        while stack:\n",
    "            start = ListNode(0)\n",
    "            layer = start\n",
    "            for _ in range(count):\n",
    "                node = stack.pop(0)\n",
    "                if node.left: \n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                layer.next = ListNode(node.val)\n",
    "                layer = layer.next\n",
    "            res.append(start.next)\n",
    "            count = len(stack)\n",
    "        return res\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "\n",
    "        rsStart = []  # 记录链表开始节点\n",
    "        rsEnd = []  # 记录链表末尾节点\n",
    "        n = 0\n",
    "        def travel(root, deep):\n",
    "            nonlocal n\n",
    "            node = ListNode(root.val)\n",
    "            if deep >= n:\n",
    "                rsStart.append(node)\n",
    "                rsEnd.append(node)\n",
    "                n += 1\n",
    "            else:\n",
    "                rsEnd[deep].next = node\n",
    "                rsEnd[deep] = node\n",
    "\n",
    "            if root.left:\n",
    "                travel(root.left, deep + 1)\n",
    "            if root.right:\n",
    "                travel(root.right, deep + 1)\n",
    "        \n",
    "        travel(tree, 0)\n",
    "        return rsStart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        if not tree:\n",
    "            return res\n",
    "        arr = [tree]\n",
    "        while arr:\n",
    "            dummy = ListNode(-1)\n",
    "            p = dummy\n",
    "            for node in arr:\n",
    "                p.next = ListNode(node.val)\n",
    "                p = p.next\n",
    "            res.append(dummy.next)\n",
    "\n",
    "            tmp = []\n",
    "            for node in arr:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "\n",
    "            arr = tmp\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        v=[tree]\n",
    "        ans=[]\n",
    "        while v:\n",
    "            l=[]\n",
    "            cur=ListNode(0)\n",
    "            y=cur\n",
    "            for x in v:\n",
    "                y.next=ListNode(x.val)\n",
    "                y=y.next\n",
    "                if x.left:\n",
    "                    l.append(x.left)\n",
    "                if x.right:\n",
    "                    l.append(x.right)\n",
    "            ans.append(cur.next)\n",
    "            v=l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        if tree is None: return res\n",
    "        que = deque([tree])\n",
    "        dummyHead = ListNode(-1)\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            pre = dummyHead\n",
    "            while size:\n",
    "                node = que.popleft()\n",
    "                pre.next = ListNode(node.val)\n",
    "                pre = pre.next\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "                size -= 1\n",
    "            res.append(dummyHead.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "  def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "    res = []\n",
    "    queue = [tree]\n",
    "    while queue:\n",
    "      head = ListNode(None)\n",
    "      now = head\n",
    "      for _ in range(len(queue)):\n",
    "        tree = queue.pop(0)\n",
    "        now.next = ListNode(tree.val)\n",
    "        now = now.next\n",
    "        if tree.left:\n",
    "          queue.append(tree.left)\n",
    "        if tree.right:\n",
    "          queue.append(tree.right)\n",
    "      res.append(head.next)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(tree)\n",
    "\n",
    "        while queue:\n",
    "            head = ListNode(-1)\n",
    "            cur = head\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                cur.next = ListNode(node.val)\n",
    "                cur = cur.next\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(head.next)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        q = deque([tree])\n",
    "        ans = []\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            head = current = ListNode(0)\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = q.popleft()\n",
    "                current.next = ListNode(node.val)\n",
    "                current = current.next\n",
    "\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "\n",
    "            ans.append(head.next)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def walk(self, root, level, di):\n",
    "        if root is None:\n",
    "            return level - 1\n",
    "        if level not in di:\n",
    "            l_node = ListNode(root.val)\n",
    "            di[level] = [l_node, l_node]\n",
    "        else:\n",
    "            l_head, l_node = di[level]\n",
    "            l_node.next = ListNode(root.val)\n",
    "            di[level] = [l_head, l_node.next]\n",
    "        lmax_d = self.walk(root.left, level + 1, di)\n",
    "        rmax_d = self.walk(root.right, level + 1, di)\n",
    "        return max(lmax_d, rmax_d)\n",
    "\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        di = {}\n",
    "        max_d = self.walk(tree, 0, di)\n",
    "        res = []\n",
    "        for i in range(max_d + 1):\n",
    "            l_head, _ = di[i]\n",
    "            res.append(l_head)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        cnt = 0\n",
    "        num_nodes = 0\n",
    "        num_childrens = 0\n",
    "        ret = []\n",
    "        if tree:\n",
    "            num_nodes = 1\n",
    "            dq = deque()\n",
    "            dq.append(tree)\n",
    "\n",
    "        head_thisLevel = None\n",
    "        p = None\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            \n",
    "            if not head_thisLevel:\n",
    "                head_thisLevel = ListNode(node.val)\n",
    "                p = head_thisLevel\n",
    "            else:\n",
    "                p.next = ListNode(node.val)\n",
    "                p = p.next\n",
    "            cnt += 1\n",
    "            if node.left:\n",
    "                dq.append(node.left)\n",
    "                num_childrens += 1\n",
    "            if node.right:\n",
    "                dq.append(node.right)\n",
    "                num_childrens += 1\n",
    "            if cnt == num_nodes:\n",
    "                ret.append(head_thisLevel)\n",
    "                head_thisLevel = None\n",
    "                p = None\n",
    "                num_nodes = num_childrens\n",
    "                num_childrens = 0\n",
    "                cnt = 0\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if tree == None:\n",
    "            return []\n",
    "        q = collections.deque([tree])\n",
    "        res = []\n",
    "        while len(q) > 0:\n",
    "            len_q = len(q)\n",
    "            head = ListNode(-1)\n",
    "            current = head\n",
    "            for i in range(len_q):\n",
    "                top = q.popleft()\n",
    "                current.next = ListNode(top.val)\n",
    "                current = current.next\n",
    "                if top.left != None:\n",
    "                    q.append(top.left)\n",
    "                if top.right != None:\n",
    "                    q.append(top.right)\n",
    "            if head.next != None:\n",
    "                res.append(head.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue = []\n",
    "        results = []\n",
    "\n",
    "        queue.append(tree)\n",
    "\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            head = ListNode()\n",
    "            pre = None\n",
    "            for i in range(length):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                nod = ListNode(node.val)\n",
    "                if i == 0:\n",
    "                    head = nod\n",
    "                if pre:\n",
    "                    pre.next = nod\n",
    "                pre = nod\n",
    "                \n",
    "                if i == length-1:\n",
    "                    nod.next = None\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            results.append(head)\n",
    "\n",
    "        return results\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ret = []\n",
    "        queue = [(tree, 0)]\n",
    "        head = 0\n",
    "        tail = 1\n",
    "        while head < tail:\n",
    "            if queue[head][0].left:\n",
    "                queue.append((queue[head][0].left, queue[head][1] + 1))\n",
    "                tail += 1\n",
    "            if queue[head][0].right:\n",
    "                queue.append((queue[head][0].right, queue[head][1] + 1))\n",
    "                tail += 1\n",
    "            head += 1\n",
    "            cur = queue[0][0]\n",
    "        for i in range(tail):\n",
    "            if i == 0:\n",
    "                ret.append(ListNode(queue[i][0].val))\n",
    "                continue\n",
    "            if queue[i][1] == queue[i - 1][1]:\n",
    "                cur.next = ListNode(queue[i][0].val)\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                ret.append(ListNode(queue[i][0].val))\n",
    "                cur = ret[-1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]: # 用队列实现广度优先算法\n",
    "\n",
    "        que = collections.deque()\n",
    "        que.append(tree)\n",
    "        res = []\n",
    "        while que:\n",
    "            temp = ListNode(0)\n",
    "            dummy = temp\n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                temp.next = ListNode(node.val) # 当前层节点的val，记录在temp\n",
    "                temp = temp.next\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "            # 结束这一层，就记录这一层的结果\n",
    "            res.append(dummy.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue=[tree]\n",
    "        res=[]\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                node=queue.pop(0)\n",
    "                #不能在这里写mynode=ListNode(node.val),这样每次都新建了，也就是断开了\n",
    "                if i==0:\n",
    "                    mynode=ListNode(node.val)\n",
    "                    res.append(mynode)\n",
    "                if i<size-1:\n",
    "                    next_node=ListNode(queue[0].val)\n",
    "                    mynode.next=next_node\n",
    "                    mynode=next_node\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue = [tree]\n",
    "        ans = []\n",
    "        while len(queue) != 0:\n",
    "            virtual = ListNode(0)\n",
    "            head = virtual\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node == None:\n",
    "                    continue\n",
    "                temp.extend([node.left, node.right])\n",
    "                head.next = ListNode(node.val)\n",
    "                head = head.next\n",
    "            queue = temp\n",
    "            if virtual.next != None:\n",
    "                ans.append(virtual.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "from collections import deque\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        result_list = []\n",
    "        \n",
    "        level_nodes = deque()\n",
    "        if tree.val is not None:\n",
    "            level_nodes.append(tree)\n",
    "        while len(level_nodes)!=0:\n",
    "\n",
    "            start_node = ListNode(None) # start void node\n",
    "            cur_node = start_node\n",
    "            size_level = len(level_nodes)\n",
    "            \n",
    "            for _ in range(size_level):\n",
    "\n",
    "                node = level_nodes.popleft()\n",
    "                if(node.left is not None):\n",
    "                    level_nodes.append(node.left)\n",
    "                if(node.right is not None):\n",
    "                    level_nodes.append(node.right)\n",
    "\n",
    "                cur_node.next = ListNode(node.val)\n",
    "                cur_node = cur_node.next\n",
    "\n",
    "            result_list.append(start_node.next)\n",
    "        return result_list\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        if not tree:\n",
    "            return ans\n",
    "        q = [[tree]]\n",
    "        while q[0]:\n",
    "            thislevel = q.pop(0)\n",
    "            head = dummy = ListNode(0)\n",
    "            nextlevel = []\n",
    "            for node in thislevel:\n",
    "                head.next = ListNode(node.val)\n",
    "                head = head.next\n",
    "                if node.left:\n",
    "                    nextlevel.append(node.left)\n",
    "                if node.right:\n",
    "                    nextlevel.append(node.right)\n",
    "            ans.append(dummy.next)\n",
    "            q.append(nextlevel)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        queue = []\n",
    "        if not tree:\n",
    "            return []\n",
    "        rst = []\n",
    "        queue.append(tree)\n",
    "        dummy = ListNode(-1)\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            p = dummy\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "                p.next = ListNode(node.val)\n",
    "                p = p.next\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            rst.append(dummy.next)\n",
    "            dummy.next = None\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(tree)\n",
    "\n",
    "        while queue:\n",
    "            head = ListNode(-1)\n",
    "            cur = head\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                cur.next = ListNode(node.val)\n",
    "                cur = cur.next\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(head.next)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = deque([(root, 0)])  # 初始根节点和深度为0\n",
    "        result = []  # 存储结果\n",
    "        \n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            \n",
    "            if len(result) < depth + 1:\n",
    "                result.append(None)\n",
    "            \n",
    "            new_node = ListNode(node.val)\n",
    "            if result[depth] is None:\n",
    "                result[depth] = new_node\n",
    "            else:\n",
    "                current = result[depth]\n",
    "                while current.next:\n",
    "                    current = current.next\n",
    "                current.next = new_node\n",
    "            \n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        \n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        return self.BFS(tree)\n",
    "\n",
    "    def BFS(self, tree):\n",
    "        que = collections.deque([tree])\n",
    "        res = []\n",
    "        while que:\n",
    "            sz = len(que)\n",
    "            t = ListNode(-1)\n",
    "            p = t\n",
    "            for i in range(sz):\n",
    "                node = que.popleft()\n",
    "                q = ListNode(node.val)\n",
    "                p.next = q\n",
    "                p = p.next\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            res.append(t.next)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        q = deque()\n",
    "        q.append(tree)\n",
    "        while q:\n",
    "            dummy = ListNode(None) \n",
    "            p = dummy\n",
    "            for _ in range(len(q)): \n",
    "                treenode = q.popleft()\n",
    "                listnode = ListNode(treenode.val) \n",
    "                p.next = listnode\n",
    "                p = p.next\n",
    "                if treenode.left: q.append(treenode.left)\n",
    "                if treenode.right: q.append(treenode.right)\n",
    "            res.append(dummy.next)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        answer = []\n",
    "\n",
    "        if tree != None:\n",
    "            stack = [tree]\n",
    "            while stack:\n",
    "                tmp = []\n",
    "                for x in stack:\n",
    "                    node = ListNode(val=x.val)\n",
    "                    tmp.append(node)\n",
    "                last = None\n",
    "                while tmp:\n",
    "                    node = tmp.pop(-1)\n",
    "                    node.next = last\n",
    "                    last = node\n",
    "                answer.append(last)\n",
    "                \n",
    "                _list = []\n",
    "                for x in stack:\n",
    "                    if x.left != None:\n",
    "                        _list.append(x.left)\n",
    "                    if x.right != None:\n",
    "                        _list.append(x.right)\n",
    "                stack[:] = _list[:]\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        arr = []\n",
    "        q = [tree]\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            head = ListNode()\n",
    "            cur = head\n",
    "            for _ in range(size):\n",
    "                node = q.pop(0)\n",
    "                lnode = ListNode(node.val)\n",
    "                cur.next = lnode\n",
    "                cur = cur.next\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            arr.append(head.next)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if tree is None:\n",
    "            return []\n",
    "        traversal = []\n",
    "        node_queue, level_queue = [tree], [0]\n",
    "        current_level, head = -1, -1\n",
    "        temp = None\n",
    "        while head + 1 < len(node_queue):\n",
    "            head += 1\n",
    "            node, level = node_queue[head], level_queue[head]\n",
    "            if level != current_level:\n",
    "                traversal.append(ListNode(node.val))\n",
    "                temp = traversal[-1]\n",
    "                current_level = level\n",
    "            else:\n",
    "                temp.next = ListNode(node.val)\n",
    "                temp = temp.next\n",
    "            if node.left is not None:\n",
    "                node_queue.append(node.left)\n",
    "                level_queue.append(level + 1)\n",
    "            if node.right is not None:\n",
    "                node_queue.append(node.right)\n",
    "                level_queue.append(level + 1)\n",
    "        return traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        def dfs(root, dep):\n",
    "            if not root: return\n",
    "            mp[dep].append(root.val)\n",
    "            dfs(root.left, dep + 1)\n",
    "            dfs(root.right, dep + 1)\n",
    "\n",
    "        if not tree: return []\n",
    "        mp = defaultdict(list)\n",
    "        dfs(tree, 0)\n",
    "\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while mp[i]:\n",
    "            j = 0\n",
    "            head = cur = ListNode(-1)\n",
    "            while j < len(mp[i]):\n",
    "                cur.next = ListNode(mp[i][j])\n",
    "                cur = cur.next\n",
    "                j += 1\n",
    "            ans.append(head.next)\n",
    "            i += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        d = deque()\n",
    "        d.append(tree)\n",
    "        ans = []\n",
    "        while d:\n",
    "            end = head = ListNode()\n",
    "            for i in range(len(d)):\n",
    "                cur = d.popleft()\n",
    "                end.next = ListNode(cur.val)\n",
    "                end = end.next\n",
    "                if cur.left:\n",
    "                    d.append(cur.left)\n",
    "                if cur.right:\n",
    "                    d.append(cur.right)\n",
    "            ans.append(head.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        def dfs(node, level):\n",
    "            if not node: return None\n",
    "            if len(ans) == level:\n",
    "                ans.append(ListNode(node.val))\n",
    "            else:\n",
    "                head = ListNode(node.val)\n",
    "                head.next = ans[level]\n",
    "                ans[level] = head\n",
    "            dfs(node.right, level + 1)\n",
    "            dfs(node.left, level + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        '''\n",
    "        广度优先搜索\n",
    "        '''\n",
    "        res = []\n",
    "        q = collections.deque()\n",
    "\n",
    "        q.append(tree)\n",
    "\n",
    "        while q:\n",
    "            head = ListNode(-1)\n",
    "            cur = head \n",
    "\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                cur.next = ListNode(node.val)\n",
    "                cur = cur.next \n",
    "\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "\n",
    "                \n",
    "            res.append(head.next)\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        def dfs(node, level):\n",
    "            if not node: return None\n",
    "            if len(ans) == level:\n",
    "                ans.append(ListNode(node.val))\n",
    "            else:\n",
    "                head = ListNode(node.val)\n",
    "                head.next = ans[level]\n",
    "                ans[level] = head\n",
    "            dfs(node.right, level + 1)\n",
    "            dfs(node.left, level + 1)\n",
    "        dfs(root, 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "\n",
    "        q = deque([tree])\n",
    "        sz = len(q)\n",
    "\n",
    "        while q:\n",
    "            hair = ListNode(-1)\n",
    "            head = hair\n",
    "            sz_t = 0\n",
    "            for i in range(sz):\n",
    "                tnode = q.popleft()\n",
    "                lnode = ListNode(tnode.val)\n",
    "                head.next = lnode\n",
    "                head = head.next\n",
    "                if tnode.left:\n",
    "                    q.append(tnode.left)\n",
    "                    sz_t += 1\n",
    "                if tnode.right:\n",
    "                    q.append(tnode.right)\n",
    "                    sz_t += 1\n",
    "            sz = sz_t\n",
    "            res.append(hair.next)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if tree==None:\n",
    "            return []\n",
    "        res=[]\n",
    "        queue=[tree]\n",
    "        while queue!=[]:\n",
    "            end=queue[-1]\n",
    "            head=None\n",
    "            tail=None\n",
    "            while 1:\n",
    "                tmp=queue.pop(0)\n",
    "                if tmp.left:\n",
    "                    queue.append(tmp.left)\n",
    "                if tmp.right:\n",
    "                    queue.append(tmp.right)\n",
    "                if tmp==end:\n",
    "                    if head==None:\n",
    "                        head=ListNode(tmp.val)\n",
    "                        tail=head\n",
    "                    else:\n",
    "                        tail.next=ListNode(tmp.val)\n",
    "                        tail=tail.next\n",
    "                    res.append(head)\n",
    "                    break\n",
    "                else:\n",
    "                    if head==None:\n",
    "                        head=ListNode(tmp.val)\n",
    "                        tail=head\n",
    "                    else:\n",
    "                        tail.next=ListNode(tmp.val)\n",
    "                        tail=tail.next\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        floor = deque()\n",
    "        floor.append(tree)\n",
    "        ans = []\n",
    "\n",
    "        while floor:\n",
    "            n = len(floor)\n",
    "            head =  ListNode(None)\n",
    "            h1 = head\n",
    "            for i in range(n):\n",
    "                root = floor.popleft()\n",
    "                listnode = ListNode(root.val)\n",
    "                h1.next = listnode\n",
    "                h1 = h1.next\n",
    "                if root.left:\n",
    "                    floor.append(root.left)\n",
    "                if root.right:\n",
    "                    floor.append(root.right)\n",
    "            ans.append(head.next)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return None\n",
    "\n",
    "        ans = []\n",
    "        temp = [tree]\n",
    "\n",
    "        while temp:\n",
    "            n = len(temp)\n",
    "            new_temp = []\n",
    "            cur = head = ListNode(0)\n",
    "            for i in range(n):\n",
    "                node = temp.pop(0)\n",
    "                head.next = ListNode(val=node.val)\n",
    "                head = head.next\n",
    "                if node.left:\n",
    "                    new_temp.append(node.left)\n",
    "                if node.right:\n",
    "                    new_temp.append(node.right)\n",
    "            head.next = None\n",
    "            ans.append(cur.next)\n",
    "            temp = new_temp\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        if not tree:\n",
    "            return []\n",
    "        queue=deque([tree])\n",
    "        res=[]\n",
    "        while queue:\n",
    "            n=len(queue)\n",
    "            dummy=ListNode(-1)\n",
    "            p=dummy\n",
    "            for i in range(n):\n",
    "                cur=queue.popleft()\n",
    "                newNode=ListNode(cur.val)\n",
    "                p.next=newNode\n",
    "                p=p.next\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            res.append(dummy.next)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        nodes = self.process(tree, 0, [])\n",
    "        for i in range(len(nodes)):\n",
    "            if len(nodes[i]) > 1:\n",
    "                head = ListNode(nodes[i][0], next=ListNode())\n",
    "                k = 0\n",
    "                cur = head\n",
    "                while k < len(nodes[i]) - 1:\n",
    "                    cur.val = nodes[i][k]\n",
    "                    cur.next = ListNode(nodes[i][k + 1])\n",
    "                    cur = cur.next\n",
    "                    k += 1\n",
    "                    print(cur, head)\n",
    "            elif len(nodes[i]) == 1:\n",
    "                head = ListNode(nodes[i][0])\n",
    "            else:\n",
    "                head = None\n",
    "            res.append(head)\n",
    "        return res\n",
    "    def process(self, cur, cnt, nodes):\n",
    "        if cur == None:\n",
    "            return nodes\n",
    "        if cnt >= len(nodes):\n",
    "            nodes.append([])\n",
    "        if cur.left == None and cur.right == None:\n",
    "            nodes[cnt].append(cur.val)\n",
    "            return nodes\n",
    "        nodes[cnt].append(cur.val)\n",
    "        nodes = self.process(cur.left, cnt + 1, nodes)\n",
    "        nodes = self.process(cur.right, cnt + 1, nodes)\n",
    "        return nodes\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "import collections\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        ans=[]\n",
    "        dqe=collections.deque([tree])\n",
    "        while dqe:\n",
    "            size,p=len(dqe),ListNode(0)\n",
    "            cur=p\n",
    "            for _ in range(size):\n",
    "                tmp=dqe.popleft()\n",
    "                cur.next=ListNode(tmp.val)\n",
    "                cur=cur.next\n",
    "                if tmp.left:\n",
    "                    dqe.append(tmp.left)\n",
    "                if tmp.right:\n",
    "                    dqe.append(tmp.right)\n",
    "            cur.next=None\n",
    "            ans.append(p.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        res = []\n",
    "        q = deque()\n",
    "        q.append(tree)\n",
    "        while q:\n",
    "            dummy = ListNode(None) \n",
    "            p = dummy\n",
    "            for _ in range(len(q)): \n",
    "                treenode = q.popleft()\n",
    "                listnode = ListNode(treenode.val) \n",
    "                p.next = listnode\n",
    "                p = p.next\n",
    "                if treenode.left: q.append(treenode.left)\n",
    "                if treenode.right: q.append(treenode.right)\n",
    "            res.append(dummy.next) \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        heads = []\n",
    "        tails = []\n",
    "        self.collectListByDepth(tree, 0, heads, tails)\n",
    "        return heads\n",
    "\n",
    "    def collectListByDepth(self, tree, depth, heads, tails):\n",
    "        if tree is None:\n",
    "            return\n",
    "\n",
    "        node = ListNode(tree.val)\n",
    "\n",
    "        if depth < len(tails):\n",
    "            tails[depth].next = node\n",
    "            tails[depth] = node\n",
    "        else:\n",
    "            heads.append(node)\n",
    "            tails.append(node)\n",
    "        \n",
    "        self.collectListByDepth(tree.left, depth+1, heads, tails)\n",
    "        self.collectListByDepth(tree.right, depth+1, heads, tails)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:\n",
    "        list1 = []\n",
    "        list2 = [1, ]\n",
    "        Solution().preorder_tree(list1, list2, tree)\n",
    "        print('list1=', list1)\n",
    "        print('list2=', list2)\n",
    "        new_ls = []\n",
    "        m = 0\n",
    "        while list1:\n",
    "            node = ListNode(0)\n",
    "            tmp_node = node\n",
    "            i = list1[0:list2[m]]\n",
    "            print('i=', i)\n",
    "            n = 0\n",
    "            while tmp_node:\n",
    "                if n == len(i) - 1:\n",
    "                    tmp_node.next = ListNode(i[n])\n",
    "                    print('node=', tmp_node.next.val)\n",
    "                    break\n",
    "                tmp_node.next = ListNode(i[n])\n",
    "                print('node=', tmp_node.next.val)\n",
    "                n += 1\n",
    "                tmp_node = tmp_node.next\n",
    "            new_ls.append(node.next)\n",
    "            list1 = list1[list2[m]:]\n",
    "            m += 1\n",
    "            print('lst=', list1)\n",
    "            if m > len(list2) - 1:\n",
    "                break\n",
    "        return new_ls\n",
    "\n",
    "    def preorder_tree(self, lst, cir, tree: TreeNode):\n",
    "        # if tree is None:\n",
    "        #     return\n",
    "        stack = deque([tree])\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        next_level = []\n",
    "        while stack:\n",
    "            node = 0\n",
    "            current_node = stack.popleft()\n",
    "            if i == 0:\n",
    "                lst.append(current_node.val)\n",
    "                i += 1\n",
    "                cnt -= 1\n",
    "            if current_node.left:\n",
    "                stack.append(current_node.left)\n",
    "                lst.append(current_node.left.val)\n",
    "                node += 1\n",
    "            if current_node.right:\n",
    "                stack.append(current_node.right)\n",
    "                lst.append(current_node.right.val)\n",
    "                node += 1\n",
    "            cnt += 1\n",
    "            next_level.append(node)\n",
    "            print('cnt=', cnt)\n",
    "            print('next_level1=', next_level)\n",
    "            if cnt == sum(next_level[0:i]):\n",
    "                cir.append(cnt)\n",
    "                next_level = next_level[i:]\n",
    "                i = cnt\n",
    "                print('i=', i)\n",
    "                cnt = 0\n",
    "                continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        def dfs(node, level):\n",
    "            if not node: return None\n",
    "            if len(ans) == level:\n",
    "                ans.append(ListNode(node.val))\n",
    "            else:\n",
    "                head = ListNode(node.val)\n",
    "                head.next = ans[level]\n",
    "                ans[level] = head\n",
    "            dfs(node.right, level + 1)\n",
    "            dfs(node.left, level + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def listOfDepth(self, root: TreeNode) -> List[ListNode]:\n",
    "        ans = []\n",
    "        def dfs(node, level):\n",
    "            if not node: return None\n",
    "            if len(ans) == level:\n",
    "                ans.append(ListNode(node.val))\n",
    "            else:\n",
    "                head = ListNode(node.val)\n",
    "                head.next = ans[level]\n",
    "                ans[level] = head\n",
    "            dfs(node.right, level + 1)\n",
    "            dfs(node.left, level + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
